APPROACH TO SOLVE A PSEUDOGEOMETRIC VERSION OF THE TRAVELING SALESMAN PROBLEM

Makarkin Sergey Borisovich, Associate professor, sub-department of applied mathematics and informatics, Togliatti State University (14 Belorusskaya street, Togliatti, Russia), s.makarkin@gmail.com
Mel'nikov Boris Feliksovich, Doctor of physical and mathematical sciences, professor, sub-department of applied mathematics and informatics, Togliatti State University (14 Belorusskaya street, Togliatti, Russia), barmaley62@yandex.ru
Trenina Marina Anatol'evna, Senior lecturer, sub-department of applied mathematics and informatics, Togliatti State University (14 Belorusskaya street, Togliatti, Russia), trenina.m.a@gmail.com

004.23

Background. The traveling salesman problem is an example of a mathematical model that, being created in one subject area, finds application in many other areas. The pseudogeometric version of this problem more adequately describes a set of its private cases, encountered in most subject areas, in comparison with a more widelyused geometric version. The aim of the work is to apply the developed approaches to solve the geometric version of the traveling salesman problem for its so-called pseudogeometric version.
Materials and methods. To solve the pseudogeometric problem of traveling salesman the authors considered several randomly generated rearrangement of a set of dots, and for each one they applied the algorithm of pseudorestoration of their disposition. The choice of the only variant of disposition of each dot is possible after solution of the optimization problem, consisting in the turn of the generated set of dots through a certain angle and the shift along a certain vector.
Results. The authors formulated various metrics and studied the properties thereof, on the basis of which they have developed a heuristic algorithm of local search.
Conclusions. Applications of the metrics and the heuristic algorithm of local search, described in the paper, increased the efficiency of the geometric method of solution of the pseudogeometric problem of traveling salesman.

traveling salesman problem, geometric version, pseudogeometric version, geometric approach, metrics, heuristic algorithms.

1. Makarkin S. B., Mel'nikov B. F. Stokhasticheskaya optimizatsiya v informatike [Stochastic optimization in informatics]. 2013, vol. 9, no. 2, pp. 54–72.
2. Makarkin S. B., Mel'nikov B. F., Trenina M. A. Stokhasticheskaya optimizatsiya v informatike [Stochastic optimization in informatics]. 2014, vol. 10, iss. 1, pp. 63–71.
3. Hromkovic J. Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer, 2003, 538 p.
4. Melnikov B., Radionov A., Gumayunov V. Proc. of 8th International Conference on Enterprise Information Systems, ICEIS-2006. P. 360–364.
5. Mel'nikov B., Romanov N. Teoreticheskie problemy informatiki i ee prilozheniy [Theoretical problems of informatics and its applications]. 2001, no. 4, pp. 81–92.
6. Melnikov B. Cybernetics and Systems Analysis. 2006, vol. 42, no. 3 (Sept.), pp. 335–341.
7. Mel'nikov B. F., Mel'nikova E. A. Sistemy upravleniya i informatsionnye tekhnologii [Control systems and information technologies]. 2007, no. 2 (28), pp. 16–20.
8. The Traveling Salesman problem. G. Gutin, A. Punnen (editors). Kluwer Academic Publishers, 2002.
9. Available at: http://arxiv.org/ftp/arxiv/papers/1204/1204.2350.pdf – Liew Sing. Introducing convex layers to the Traveling Salesman Problem. Preprint: arXiv: 1204.2348. 2012. (Access mode – free.)
10. Somhom S., Modares A., Enkawa T. Computers & Operations Research. 1999, vol. 26, no. 4, pp. 395–407.
11. Gromkovich Yu. Teoreticheskaya informatika. Vvedenie v teoriyu avtomatov, teoriyu vychislimosti, teoriyu slozhnosti, teoriyu algoritmov, randomizatsiyu, teoriyu svyazi i kriptografiyu: per. s nem. [Theoretical informatics. Introduction into the theory of automata, theory of computability, theory of algorithms, randomization, theory of communication cryptography: translation from German]. Saint-Petersburg: BKhVPeterburg, 2010, 326 p.
12. Kolmogorov A. N., Fomin S. V. Elementy teorii funktsiy i funktsional'nogo analiza [Elements of functional analysis and the theory of functions]. 7th ed. Moscow: Fizmatlit, 2004, 570 p.